home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1993 July / InfoMagic USENET CD-ROM July 1993.ISO / sources / unix / volume5 / bm.odd < prev    next >
Encoding:
Internet Message Format  |  1986-11-30  |  10.5 KB
  1. Subject: bm - odd address optimization
  2. Newsgroups: mod.sources
  3. Approved: jpn@panda.UUCP
  4.  
  5. Mod.sources:  Volume 5, Issue 16
  6. Submitted by: talcott!topaz!lll-crg!csustan!casey
  7.  
  8. [ I haven't tried this, but I bet you odd-address-machine people will
  9.   be happy to see this fix - moderator
  10. ]
  11.  
  12. Hi,
  13.   I've just recently porteed bm to a PDP-11 runnung under the August seismo
  14. distribution of BSD2.9.  It turns out this wasn't an easy process at all and
  15. I was more that 3 hours into it before I found out why bm ran correctly, but
  16. almost 4 times slower than fgrep!  The problem was bm doing I/O on odd
  17. addresses and/or going for odd length transfers.  The problem rests partially
  18. with the PDP-11 architecture and partially with the implementation of copyout
  19. in the kernel.  I'll be fixing copyout (and copyin of course), but the PDP's
  20. architectual problems remain.  And as the PDP isn't the only machine that
  21. has biases about odd addresses, I thought I'd forward on the necessary changes
  22. to you.  Hope these are useful!
  23.  
  24. Leith (Casey) Leedom                lll-crg.arpa!csustan!casey
  25. Computer Science Department            work: (209) 667-3185
  26. California State University, Stanislaus        home: (209) 634-2775
  27. Turlock, CA  95380
  28.  
  29. P.S.  I'm only forwarding bm.c, Execute.c, and MoveResidue.c as they're the
  30.     only one's that needed changing.
  31.  
  32. ---- cut here ---- cut here ---- cut here ---- cut here ---- cut here ----
  33. #! /bin/sh
  34. # This is a shell archive, meaning:
  35. # 1. Remove everything above the #! /bin/sh line.
  36. # 2. Save the resulting text in a file.
  37. # 3. Execute the file with /bin/sh (not csh) to create:
  38. #    Execute.c
  39. #    MoveResidue.c
  40. #    bm.c
  41. # This archive created: Fri May 23 05:39:21 1986
  42. export PATH; PATH=/bin:/usr/bin:$PATH
  43. if test -f 'Execute.c'
  44. then
  45.     echo shar: "will not over-write existing file 'Execute.c'"
  46. else
  47. cat << \SHAR_EOF > 'Execute.c'
  48. #include <stdio.h>
  49. #include "bm.h"
  50. #include "Extern.h"
  51. Execute(DescVec, NPats, TextFile, Buffer)
  52. struct PattDesc *DescVec[]; /* pointers to status vectors for the different
  53.     * patterns, including skip tables, position in buffer, etc. */
  54. int NPats; /* number of patterns */
  55. char Buffer[]; /* holds text from file */
  56. int TextFile; /* file to search */
  57. {
  58.     long BuffPos; /* offset of first char in Buffer in TextFile */
  59.     int NRead, /* number of chars read from file */
  60.         NWanted, /* number of chars wanted */
  61.         NAvail, /* number of chars actually read */
  62.         BuffSize, /* number of chars in buffer */
  63.         BuffEx, /* flag to indicate that buffer has been searched */
  64.         ResSize,
  65.         /* number of characters in the last, incomplete line */
  66.         Found, /* flag indicates whether pattern found
  67.         * completely and all matches printed */
  68.         Valid; /* was the match "valid", i.e. if -x used,
  69.         * did the whole line match? */
  70.     char *BuffEnd; /* pointer to last char of last complete line */
  71.  
  72.     /*
  73.      * In order to optimize I/O for some machines which impose a severe
  74.      * penalty for I/O on an odd address, we play a nasty game.  First, we
  75.      * assume that the Buffer which is passed to us has an even address.
  76.      * Then whenever we move a buffer residual back to the beginning of
  77.      * the Buffer for the next read cycle, we actually move it to Buffer +
  78.      * Odd(Residual) where Odd() is 1 if Residual is odd, zero otherwise.
  79.      * This causes the the next read to go down on an even address.  We
  80.      * keep track of the beginning of data in the Buffer with BuffStart.
  81.      */
  82.     char *BuffStart;
  83.  
  84.     /* misc working variables */
  85. #ifdef notdef
  86.     int i;
  87. #else !notdef
  88.     register struct PattDesc    *Desc;
  89.     struct PattDesc            **Vec, **LastPatt = DescVec+NPats;
  90. #endif notdef
  91.  
  92.     /* initialize */
  93.     ResSize = 0;
  94.     Found = 0;
  95.     BuffPos = 0;
  96.     BuffStart = Buffer;
  97. #ifdef notdef
  98.     for (i=0; i < NPats; i++) {
  99.         DescVec[i] -> Success = 0;
  100.         DescVec[i] -> Start = Buffer;
  101.     } /* for */
  102. #else !notdef
  103.     for (Vec=DescVec; Vec < LastPatt; Vec++) {
  104.         Desc = *Vec;
  105.         Desc->Success = 0;
  106.         Desc->Start = Buffer;
  107.     }
  108. #endif notdef
  109.     /* now do the searching */
  110.     do {
  111.         /* first, read a bufferfull and set up the variables */
  112.         /*
  113.          * Some systems *even* get upset when you ask for an odd read
  114.          * length - ARGH!
  115.          */
  116.         NWanted = (int)((unsigned)(MAXBUFF - ResSize) & ~1);
  117.         NRead = 0;
  118.         do {
  119.             /*
  120.              * BuffStart+ResSize+BRead is even first time through
  121.              * this loop - afterwards, no guaranties, but for
  122.              * files this loop never goes more than once ...
  123.              * Can't do any better.
  124.              */
  125.             NAvail =
  126.                read(TextFile,BuffStart + ResSize + NRead, NWanted);
  127.             if (NAvail == -1) {
  128.                 fprintf(stderr,
  129.                   "bm: error reading from input file\n");
  130.                 exit(2);
  131.             } /* if */
  132.             NRead += NAvail; NWanted -= NAvail;
  133.         } while (NAvail && NWanted);
  134.         BuffEx = 0;
  135.         BuffSize = ResSize + NRead;
  136.         BuffEnd = BuffStart + BuffSize - 1;
  137.         /* locate the end of the last complete line */
  138.         while (*BuffEnd != '\n' && BuffEnd >= BuffStart)
  139.             --BuffEnd;
  140.         if (BuffEnd < BuffStart)
  141.             BuffEnd = BuffStart + BuffSize - 1;
  142.         while (!BuffEx) { /* work through one buffer full */
  143.             BuffEx = 1; /* set it provisionally, then clear
  144.             * it if we find the buffer non-empty */
  145. #ifdef notdef
  146.             for (i=0; i< NPats; i++) {
  147.                 if (!DescVec[i]->Success)
  148.                 /* if the pattern  has not been found */
  149.                     DescVec[i]-> Success =
  150.                     Search(DescVec[i]->Pattern,
  151.                     DescVec[i]->PatLen, BuffStart, BuffEnd,
  152.                     DescVec[i]->Skip1, DescVec[i]->Skip2,
  153.                     DescVec[i]);
  154.                 if (DescVec[i]->Success){
  155.                 /* if a match occurred */
  156.                     BuffEx = 0;
  157.                     Valid = MatchFound(DescVec[i],BuffPos,
  158.                     BuffStart, BuffEnd);
  159.                     Found |= Valid;
  160.                     if ((sFlag || lFlag) && Found)
  161.                         return(0);
  162.                 } /* if */
  163.             } /* for */
  164. #else !notdef
  165.             for (Vec=DescVec; Vec < LastPatt; Vec++) {
  166.                 Desc = *Vec;
  167.                 if (!Desc->Success)
  168.                 /* if the pattern  has not been found */
  169.                     Desc-> Success =
  170.                     Search(Desc->Pattern,
  171.                     Desc->PatLen, BuffStart, BuffEnd,
  172.                     Desc->Skip1, Desc->Skip2,
  173.                     Desc);
  174.                 if (Desc->Success){
  175.                 /* if a match occurred */
  176.                     BuffEx = 0;
  177.                     Valid = MatchFound(Desc,BuffPos,
  178.                     BuffStart, BuffEnd);
  179.                     Found |= Valid;
  180.                     if ((sFlag || lFlag) && Found)
  181.                         return(0);
  182.                 } /* if */
  183.             } /* for */
  184. #endif notdef
  185.         } /* while */
  186.         if(NRead) {
  187.             ResSize = MoveResidue(DescVec,NPats,Buffer,&BuffStart,BuffEnd);
  188.             BuffPos += BuffSize - ResSize;
  189.         } /* if */
  190.     } while (NRead);
  191.     return(!Found);
  192. } /* Execute */
  193. SHAR_EOF
  194. fi
  195. if test -f 'MoveResidue.c'
  196. then
  197.     echo shar: "will not over-write existing file 'MoveResidue.c'"
  198. else
  199. cat << \SHAR_EOF > 'MoveResidue.c'
  200. #include "bm.h"
  201. /* Moves the text which has not been completely searched at the end of
  202. * the buffer to the beginning of the buffer
  203. * and returns number of bytes moved */
  204.  
  205. /*
  206.  * In coordination with the I/O optimization code in Execute, if the Residual
  207.  * is odd in length, we move it to Buffer+1, otherwise to Buffer+0, to make
  208.  * sure that [at least] the next read goes down on an even address.  A pointer
  209.  * to a pointer to the current start of data in the buffer is passed in, that
  210.  * pointer is updated and passed back.
  211.  */
  212.  
  213. int MoveResidue(DescVec, NPats, Buffer, BuffStartP, BuffEnd)
  214. struct PattDesc *DescVec[];
  215. int NPats;
  216. char *Buffer, **BuffStartP, *BuffEnd;
  217. {
  218.     char *FirstStart, *f, *t, *Residue;
  219.     int ResSize, i;
  220.     FirstStart = BuffEnd;
  221.     /* find the earliest point which has not been
  222.     * completely searched */
  223.     for (i=0; i < NPats; i++) {
  224.         FirstStart = 
  225.             min(FirstStart, DescVec[i]-> Start );
  226.     } /* for */
  227.     /* now scan to the beginning of the line containing the
  228.     * unsearched text */
  229.     for (Residue = FirstStart; *Residue != '\n' &&
  230.     Residue >= *BuffStartP; Residue--);
  231.     if (Residue < *BuffStartP)
  232.         Residue = FirstStart;
  233.     else ++Residue;
  234.     ResSize = (BuffEnd - Residue + 1);
  235.     /* now move the residue to the beginning of
  236.     * the file */
  237.     t = *BuffStartP = ((unsigned) ResSize & 1) ? Buffer+1 : Buffer;
  238.     f = Residue;
  239.     for(i=ResSize;i;--i)
  240.         *t++ = *f++;
  241.     /* now fix the status vectors */
  242.     for (i=0; i < NPats; i++) {
  243.         DescVec[i]->Start -= (Residue - *BuffStartP);
  244.     } /* for */
  245.     return(ResSize);
  246. } /* MoveResidue */
  247. SHAR_EOF
  248. fi
  249. if test -f 'bm.c'
  250. then
  251.     echo shar: "will not over-write existing file 'bm.c'"
  252. else
  253. cat << \SHAR_EOF > 'bm.c'
  254. #include <stdio.h>
  255. #include <sys/types.h>        /* XXXX ADDED FOR BSD2.9 */
  256. #include <sys/file.h>
  257. #include <strings.h>
  258. #include "bm.h"
  259. #include "Extern.h"
  260. main(argc,argv)
  261. int argc;
  262. char *argv[];
  263. {
  264.     /* test driver for grep based on Boyer-Moore algorithm */
  265.     char BigBuff[MAXBUFF + 3];
  266.     /*
  267.     * We leave one extra character at the beginning and end of the buffer,
  268.     * but don't tell Execute about it. This is so when someone is
  269.     * scanning the buffer and scans past the end (or beginning)
  270.     * we are still technically in the buffer (picky, but there ARE
  271.     * machines which would complain).  We then leave an *additional*
  272.     * free byte at the begining so we can pass an even address to Execute
  273.     * (on some machines, odd address I/O can *COMPLETELY* destroy any
  274.     * speed benefits of bm).
  275.     */
  276.     int ret = 1, /* return code from Execute */
  277.         NotFound = 0, /* non-zero if file not readable */
  278.         NFiles,
  279.         NPats; /* number of patterns to search for */
  280.     char i,
  281.         *FlagPtr,
  282.         **OptPtr; /* used to scan command line */
  283.     int TextFile /* file to search */;
  284.     struct PattDesc *DescVec[MAXPATS];
  285.  
  286.     --argc;
  287.     OptPtr = argv + 1;
  288.     while ( argc && **OptPtr == '-') {
  289.         FlagPtr = *OptPtr + 1;
  290.         while (*FlagPtr) {
  291.             switch (*FlagPtr) {
  292.                 case 'c': cFlag = 1; break;
  293.                 case 'e': eFlag = 1;
  294.                     /* get the patterns from next arg */
  295.                     NPats = MkDescVec(DescVec,*++OptPtr);
  296.                     --argc;
  297.                     break;
  298.                 case 'f': fFlag = 1; 
  299.                     /* read the patterns from a file */
  300.                     NPats = GetPatFile(*++OptPtr,DescVec);
  301.                     --argc;
  302.                     break;
  303.                 case 'l': lFlag = 1; break;
  304.                 case 'n': nFlag = 1; break;
  305.                 case 's': sFlag = 1; break;
  306.                 case 'x': xFlag = 1; break;
  307.                 case 'h': hFlag = 1; break;
  308.                 default:
  309.                     fprintf(stderr,
  310.                     "bm: invalid option: -%c \n",
  311.                     *FlagPtr);
  312.                     PutUsage();
  313.                     exit(2);
  314.             } /* switch */
  315.             ++FlagPtr;
  316.         } /* while */
  317.         ++OptPtr; --argc;
  318.     } /* while */
  319.     /* OptPtr now points to patterns */
  320.     if (!fFlag && !eFlag) {
  321.         if (!argc) {
  322.             fprintf(stderr,"bm: no pattern specified\n");
  323.             PutUsage();
  324.             exit(2);
  325.         } else
  326.             NPats = MkDescVec(DescVec,*OptPtr);
  327.         ++OptPtr; --argc;
  328.     }
  329.     /* OptPtr now points to first file */
  330.     NFiles = argc;
  331.     if (!NFiles)
  332.         ret &= Execute(DescVec,NPats,0,BigBuff+2);
  333.     else while (argc--) {
  334.         if ((NFiles > 1) || lFlag) FileName = *OptPtr;
  335.         if ((TextFile = open(*OptPtr,O_RDONLY,0)) < 0) {
  336.             fprintf(stderr,"bm: can't open %s\n",*OptPtr);
  337.             NotFound++;
  338.         } else {
  339.             ret &= Execute(DescVec,NPats,TextFile,BigBuff+2);
  340.             if (sFlag && !ret)
  341.                 exit(0);
  342.             close(TextFile);
  343.         } /* if */
  344.         ++OptPtr;
  345.     } /* while */
  346.     if (cFlag) printf("%d\n",MatchCount);
  347.     exit(NotFound ? 2 : ret);
  348. } /* main */
  349. SHAR_EOF
  350. fi
  351. exit 0
  352. #    End of shell archive
  353.  
  354.  
  355.